1.5 Quantum parallelism

Feynman的想法在1985年被David Deutsch解释地更具体，Deutsch指出量子计算机的潜能在于量子并行性(quantum parallelism)。考虑一个黑盒，可以将一个比特$x$映射到另一个比特$f(x)$上，但我们不知道内部发生了什么，也许计算过程很复杂，因为它耗时24小时。一共有四种可能的函数映射关系$f(x)$，我们想要知道这个黑盒在计算什么。如果要计算$f(0)$和$f(1)$的结果，则总共要消耗两倍时间，即48小时。如果我们退一步，只想验证$f(0)=f(1)$还是$f(0)\neq f(1)$，也还是需要做两次计算，耗时48小时。

现在看看量子计算机能不能只用一次计算（耗时24小时）就能完成任务。尽管映射$f(x)$可能是不可逆的，但量子计算过程是幺正的且一定是可逆的。考虑一个从2 qubit转换到2 qubit的幺正变换： $U_f : |x\rangle|y\rangle\rightarrow|x\rangle|y\oplus f(x)\rangle .$ 其中$\oplus$代表“异或”。此操作表示，若$f(x)=1$就翻转$y$，若$f(x)=0$则不做任何操作。Deutsch问的问题是，能不能只执行一次操作就验证$f(0)$与$f(1)$到底相同还是不同？

由于黑盒是一台量子计算机，我们可以选取输入态为$|0\rangle$和$|1\rangle$的叠加态：

• 若选取第2个qubit为叠加态$|y\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$，那么映射 $U_f: |x\rangle\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\rightarrow |x\rangle\frac{1}{\sqrt{2}}(|f(x)\rangle-|1\oplus f(x)\rangle)=|x\rangle(-1)^{f(x)}\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle).$ 于是我们将$f(x)$分离到了前面系数中（与$x$有关的相位项）。

• 我们再将第1个qubit $|x\rangle$也改为另一个叠加态： $U_f:\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\rightarrow\frac{1}{\sqrt{2}}[(-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle]\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle).$

• 最后，将第一个比特投影到一组基向量$|\pm\rangle=\frac{1}{\sqrt{2}}(|0\rangle\pm|1\rangle)$上。显然，如果：

  • $f(0)=f(1)$（称作balanced function）那么我们总会得到$|+\rangle$，
  • $f(0)\neq f(1)$（称作constant function）那么我们总会得到$|-\rangle$。

就这样，我们解决了Deutsch的问题，而且发现了经典计算机和量子计算机的区别：经典计算机必须运行两次黑盒计算才能区分balanced function和constant function，但量子计算机只需要一次计算就可以完成任务。

这是因为量子计算机操作的不是单个态而是叠加态，因此可以一次获得映射函数的“全局”信息，这个信息同时依赖于$f(0)$和$f(1)$。在这个意义上我们称它具有量子并行性(quantum parallelism)。

现在假设我们对作用在N-qubit上的函数的全局性质感兴趣，此函数具有$2^N$个可能的输入，如$f(|0100...\rangle)$。要得到函数$f(x)$完整的映射表，需要执行$2^N$次$f$的计算。然而这个计算对于$N\gg1$的情况完全不可行，比如$N=100$时需要$10^{30}$次计算。但对于一个执行幺正变换 $U_f:|x\rangle|0\rangle\rightarrow|x\rangle|f(x)\rangle$ 的量子计算机来说，我们可以选取存储在输入寄存器中的初态为： $|\psi\rangle\equiv\left[\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\right]^{N}=\frac{1}{2^{N / 2}} \sum_{x=0}^{2^{N}-1}|x\rangle$ 只执行一次上述变换，产生了状态 $\frac{1}{2^{N/2}}\sum_{x=0}^{2^N-1}|x\rangle|f(x)\rangle$ 函数$f$的全局信息都包含在了这个态中，只要我们想个办法提取出来即可。

这个量子计算呈现出了“大规模量子并行性”（massive quantum parallelism）。函数再复杂都只需要计算一次，这就是量子并行性的威力。这种大规模并行性也是Shor设计因数分解算法的出发点。

正如前面提到的，量子信息是编码在物理系统不同部分之间的非局域关联（纠缠）中的，比如上述$f(x)$的信息包含在了量子计算机的输入寄存器和输出寄存器的纠缠$\frac{1}{2^{N/2}}\sum_{x=0}^{2^N-1}|x\rangle|f(x)\rangle$中。然而，提取这个非局域信息并不容易。

比如，假如我要去测量输入寄存器，它就会塌缩到某一个本征态$|x_0\rangle$，这个本征态是从$2^N$个可能的态中随机选择的。这个过程会得到状态$|x_0\rangle|f(x_0)\rangle$。我们可以继续测量输出寄存器，但只能得到测量结果$f(x_0)$。但是由于两个寄存器之间的纠缠被第一次测量破坏，我们就没有机会再通过测量去确定任何$y_0\neq x_0$的函数值$f(y_0)$了。在这种情况下，量子计算机并不比经典计算机更强大。

Deutsch问题的解决方案告诉我们，如何巧妙利用那些编码在量子非局域关联中的有效信息是设计量子算法的关键。